\section{红黑树的性质}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item
  \item \textbf{对图13-1中的红黑树，画出调用TREE-INSERT插入关键字36后的结果。如果插入的结点被标为红色，所得的树是否还是一颗红黑树？如果该结点被标为黑色呢？}

        标为红色则还是红黑树，黑色就不是了。

  \item \textbf{定义松弛红黑树为满足红黑性质1，3，4和5的二叉查找树。换言之，根部可以是红色或是黑色。考虑一棵根是红色的松弛红黑树$T$。如果将$T$的根部标为黑色而其他都不变，则所得到的是否还是一棵红黑树？}

        是

  \item \textbf{假设将一棵红黑树的每一个红结点“吸收”到它的黑色父结点中，来让红结点的子女变成黑色父结点的子女（忽略关键字的变化）。当一个黑结点的所有红色子女都被吸收后，其可能的度是多少？此结果树的叶子深度怎样？}

        可能的度有：
        \begin{itemize}
          \item 2，该结点的子女都是黑结点。
          \item 3，子女中一个黑结点，一个红结点。
          \item 4，子女都是红结点。
        \end{itemize}

        叶子的深度都一样。（根据红黑性质5）

  \item \textbf{证明：在一棵红黑树中，从某结点$x$到其后代叶结点的所有简单路径中，最长的一条是最短一条的至多两倍。}

        直观上来说，最短路径肯定全是黑结点，而最长路径肯定是红黑结点交替出现。

        由红黑性质4可以得出一条路径中至少有一半是黑结点，即$\text{bh}(x) \geqslant h/2$。于是$h \leqslant 2\text{bh}(x)$，其中$h$也是最长路径的长度，$\text{bh}(x)$也是最短路径的长度，即得证。

  \item \textbf{在一棵黑高度为$k$的红黑树中，内结点最多可能有多少个？最少可能有多少个？}

        由上题可知$h$最大为$2k$，因此内结点最多为$\sum^{2k-1}_{i=0} 2^i = 4^k - 1$。

        而$h$的最小值应为$k$，因此内结点最少为$\sum^{k-1}_{i=0} 2^i = 2^k - 1$。

  \item
\end{enumerate}

\section{旋转}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item
  \item

  \item \textbf{设在图13-2的左边一棵树中，$a$，$b$和$c$分别为子树$\alpha$，$\beta$和$\gamma$中的任意结点。如果将结点$x$左旋，则$a$，$b$和$c$的深度会如何变化？}

        $a$深度加1，$b$不变，$c$减1。
\end{enumerate}

\section{插入}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item \textbf{在RB-INSERT的第16行中，假设新插入的结点$z$是红的。注意如果将$z$着为黑色，则红黑树的性质4)就不会被破坏。那么我们为什么没有选择将$z$着为黑色呢？}

        显然着为黑色，性质5)肯定被破坏了。
\end{enumerate}

\section*{思考题}
\addcontentsline{toc}{section}{思考题}

\begin{enumerate}[label=\textbf{\thechapter{}-\arabic*}]
  \item \textbf{持久动态集合}

        \begin{enumerate}[label=\alph*)]
          \item {\kaishu 对一棵一般的持久二叉查找树，为插入一个关键字$k$或删除一个结点$y$，确定需要改变哪些结点。}

                插入一个结点需要改变途径的所有结点，删除一个结点需要改变沿该结点向上至根的所有结点。

          \item {\kaishu 请写出一个程序PERSISTENT-TREE-INSERT，使得在给定一棵持久树$T$和一个要插入的关键字$k$时，它返回将$k$插入$T$后新的持久树$T'$。}

\begin{alltt}
PERSISTENT-TREE-INSERT(\(T\), \(k\))
    用 \(root[T]\)结点构造 \(root[T']\)结点
    用 \(k\)构造结点 \(z\)
    \(x\gets{}root[T]\)
    \(y\gets{}root[T']\)
    \(a\gets\text{NIL}\)
    while \(x\ne\text{NIL}\)
        do \(a\gets{}y\)
           if \(key[z]<key[x]\)
               then 用 \(left[x]\)结点构造一个 \(tmp\)结点
                    \(left[y]\gets{}tmp\)
                    \(x\gets{}left[x]\)
                    \(y\gets{}left[y]\)
               else 用 \(right[x]\)结点构造一个 \(tmp\)结点
                    \(right[y]\gets{}tmp\)
                    \(x\gets{}right[x]\)
                    \(y\gets{}right[y]\)
    if \(a=\text{NIL}\)
        then \(root[T']\gets{}z\)
        else if \(key[z]<key[a]\)
                 then \(left[a]\gets{}z\)
                 else \(right[a]\gets{}z\)
    return \(T'\)
\end{alltt}

          \item {\kaishu 如果持久二叉查找树$T$的高度为$h$，所实现的PERSISTENT-TREE-INSERT的时间和空间要求分别是多少？（空间要求与新分配的结点数成正比。）}

                时间要求为$O(h)$，空间要求也为$O(h)$。

          \item {\kaishu 假设我们在每个结点中增加一个父亲结点域。这样一来，PERSISTENT-TREE-INSERT需要做一些额外的复制工作。证明在这种情况下，PERSISTENT-TREE-INSERT的时空要求为$\Omega(n)$，其中$n$为树中的结点个数。}

                增加父亲结点域，插入新结点时就需要复制整棵树，因此时空要求为$\Omega(n)$。

          \item {\kaishu 说明如何利用红黑树来保证每次插入或删除的最坏情况运行时间为$O(\text{lg}n)$。}
        \end{enumerate}
\end{enumerate}